from scipy.spatial.distance import euclidean
from scipy.optimize import linear_sum_assignment
from shapely.geometry import Polygon, LineString, Point
import numpy as np

def optimize_cut_path(shapes):
    """
    根据输入的形状列表优化切割路径，最小化空程路径距离。
    
    参数:
        shapes (list): Shapely Polygon 或 MultiPolygon 对象的列表。
    
    返回:
        list: 优化后的路径点列表 (x, y, is_cut)。
    """
    # 提取每个形状的质心作为路径点
    points = [(shape.centroid.x, shape.centroid.y) for shape in shapes]

    # 构造距离矩阵（欧几里得距离）
    num_points = len(points)
    distance_matrix = np.zeros((num_points, num_points))
    for i in range(num_points):
        for j in range(num_points):
            if i != j:
                distance_matrix[i, j] = euclidean(points[i], points[j])

    # 使用线性分配算法解决 TSP 近似
    row_ind, col_ind = linear_sum_assignment(distance_matrix)
    optimized_indices = row_ind[np.argsort(col_ind)]

    # 按照优化顺序重新排列路径点
    optimized_points = [points[i] for i in optimized_indices]

    # 构造完整路径，包含切割状态
    optimized_path = []
    for i, (x, y) in enumerate(optimized_points):
        is_cut = True if i < len(optimized_points) - 1 else False  # 最后一个点不切割
        optimized_path.append((x, y, is_cut))

    return optimized_path
